11115. Дядя Джек

Дядя Джек хочет раздать все свои диски племянникам. Необходимо подсчитать количество способов, которыми дядя может раздать диски племянникам. Известно, что все диски у дяди разные.

Вход. Состоит из нескольких тестов. Каждая строка содержит количество племянников n (1 £ n £ 10) и количество раздаваемых дисков d (0 £ d £ 25).

Выход. Для каждого теста вывести количество способов, которыми дядя может раздать все свои диски племянникам.

Пример входа

1 20

3 10

0 0

Пример выхода

1

59049

РЕШЕНИЕ

комбинаторика

Подсказка

1. Сколькими способами можно раздать d = 1 диск n = 5 племянникам?

2. Пусть d = 2, n = 5. Сколькими способами можно раздать первый диск племянникам? А второй диск? Сколькими способами можно раздать два диска пяти племянникам? В чем состоит правило умножения в комбинаторике?

3. Сколькими способами можно раздать три диска пяти племянникам?

4. Чему равен ответ при d = 25, n = 10? Какой тип данных следует использовать при вычислениях?

Анализ алгоритма

Каждый диск можно отдать любому из n племянников. Значит согласно комбинаторному правилу умножения d дисков можно раздать n^d способами. Поскольку наибольшее возможное значение результата 10²⁵ не входит в 64 битовый целочисленный тип, то следует реализовать длинную арифметику.

Реализация алгоритма

Реализуем возведение в степень в классе BigInteger.

class BigInteger

{

private:

enum{MAXLENGTH=100};

int m[MAXLENGTH];

int len;

public:

. . .

BigInteger pow(int n, int k)

{

int i;

BigInteger Temp(1);

for(i = 0; i < k; i++)

Temp = Temp * n;

return Temp;

}

};

Объявим переменную res типа BigInteger.

BigInteger res(1);

Для каждой входной пары n и d выводим значение n^d.

while(scanf("%d %d",&n,&d),n+d)

res.pow(n,d).print();